package graph;

import java.util.ArrayList;
//邻接表
public class AdjacencyList {
    class Node {
        int source;
        int dest;
        Node next;
        public Node(int source,int dest) {
            this.source = source;
            this.dest = dest;
        }
    }
    public char[] chars;
    public boolean isDirect;//true:有向图   false:无向图
    ArrayList<Node> link;

    public AdjacencyList(int size, boolean isDirect) {
        this.chars = new char[size];
        this.isDirect = isDirect;
        link = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            link.add(null);
        }
    }

    public void init(char[] array) {
        for (int i = 0; i < array.length; i++) {
            chars[i] = array[i];
        }
    }

    public boolean addEdge(char source, char dest, int weight) {
        int destIndex = getIndex(dest);
        int sourceIndex = getIndex(source);
        if (destIndex == -1 || sourceIndex == -1) {
            return false;//说明没有这个字符
        }
        Node h = link.get(sourceIndex);

        if(h == null){
            Node cur = new Node(sourceIndex,destIndex);
            cur.next = h;
            link.add(sourceIndex,cur);
            return true;
        }

        while (h.next != null) {
            if (h.dest == destIndex) {
                return false;
            }
            h = h.next;
        }

        if (h.dest != destIndex) {
            h.next = new Node(sourceIndex,destIndex);
            return true;
        }
        return false;
    }

    private int getIndex(char c) {
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == c) {
                return i;
            }
        }
        return -1;
    }

    public int getDevOfV(char c) {
        int count = 0;
        int sourceIndex = getIndex(c);
        Node node = link.get(sourceIndex);
        //出度
        while (node != null) {
            count++;
            node = node.next;
        }
        //入度
        if (isDirect) {
            for (int i = 0; i < link.size(); i++) {
                if (i == sourceIndex) continue;
                Node n = link.get(i);
                while (n != null) {
                    if (n.dest == sourceIndex)
                        count++;
                    n = n.next;
                }
            }
        }
        return count;
    }

    public void printGraph() {
        System.out.println(link.size());
        for (int i = 0; i < link.size() - chars.length;i++) {
            Node h = link.get(i);
            char source = chars[h.source];
            System.out.print(source + " -> ");
            while (h != null){
                System.out.print(chars[h.dest] + " -> ");
                h = h.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        AdjacencyList graph = new AdjacencyList(4, true);
        char[] array = {'A', 'B', 'C', 'D'};
        graph.init(array);
        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
        System.out.println(graph.getDevOfV('A'));
        graph.printGraph();
    }
}
